<html>
	<head>
		<title>path find by qq.d.y</title>
		<script src="../util.js"></script>
		<script src="path.js"></script>
		<script>
			var gl, W, H, g2d, mpos = '';
			var PUT_OBJ = 0, PUT_SRC = 1, PUT_DST = 2, put = PUT_OBJ;
			var dst = [NUM-1, NUM-1], src = [0, 0];
			var RUN = 0, DONE = 1;
			function init() {
				W = document.getElementById('canvas').width;
				H = document.getElementById('canvas').height;
				document.getElementById('put').value = 'barrier';
				var cv = document.getElementById('canvas');
				cv.onmousemove = on_mouse_move;
				cv.onmousedown = on_mouse_down;
				gl = cv.getContext('experimental-webgl');
				if (!gl)   alert('please do not use fuck IE...');
				gl.clearColor(0,0,0,1);
				//gl.lineWidth(8.0);   not any effect
				
				g2d = new G2D(gl, W, H);
				g2d.font_create('font.bmp');
				
				BFS.state = DONE, GOAL.state = DONE, ASTAR.state = DONE;
				
				setTimeout(render, 30);
			}
			var map_offset = [[20, 120], [340, 120], [660, 120]];
			function draw_line_on_map(id, s, e, c, z) {
				var offx = map_offset[id][0];
				var offy = map_offset[id][1];
				g2d.line(s[0]+offx, s[1]+offy, e[0]+offx, e[1]+offy, c, z);
			}
			function draw_rect_on_map(id, x, y, c) {
				var offx = map_offset[id][0];
				var offy = map_offset[id][1];
				g2d.rect(x*LEN+offx+3, y*LEN+offy+4, LEN-7, LEN-7, c, 0.9);
			}
			function step_update(algorithm) {
				if (algorithm.steps.length != 0) {
					var s = algorithm.steps.shift();
					if (s.com == DEQUEUE) {
						algorithm.map[s.y][s.x].marked = true;
						algorithm.map[s.y][s.x].inqueue = false;
					} else if (s.com == ENQUEUE) {
						algorithm.map[s.y][s.x].inqueue = true;
					} else if (s.com == CHANGEPRE) {
						algorithm.map[s.y][s.x].lastx = s.newx;
						algorithm.map[s.y][s.x].lasty = s.newy;
					}
				} else {
					algorithm.state = DONE;
				}
			}
			function draw_algorithm(algorithm, mapid) {
				// draw map
				var w = NUM*LEN;
				for (var x=0;x<NUM+1;x++) { draw_line_on_map(mapid, [x*LEN, 0], [x*LEN, w], [1,1,1], 0.9); }
				for (var y=0;y<NUM+1;y++) { draw_line_on_map(mapid, [0, y*LEN], [w, y*LEN], [1,1,1], 0.9); }
				// draw src point and dst point
				draw_rect_on_map(mapid, src[0], src[1], [0,1,0]);
				draw_rect_on_map(mapid, dst[0], dst[1], [1,1,0]);
				// draw map quad and search path
				for (var y=0; y<NUM; y++) {
					for (var x=0; x<NUM; x++) {
						if (!algorithm.map[y][x].passable)   draw_rect_on_map(mapid, x, y, [1,0,0]);
						if (algorithm.map[y][x].marked)      draw_rect_on_map(mapid, x, y, [0,0.5,1]);
						if (algorithm.map[y][x].inqueue)     draw_rect_on_map(mapid, x, y, [1,0.5,0.5]);
						if (algorithm.map[y][x].lastx != -1 && algorithm.map[y][x].lasty != -1) {
							var offset = LEN / 2;
							var x1 = offset + x*LEN;
							var y1 = offset + y*LEN;
							var x2 = offset + algorithm.map[y][x].lastx*LEN;
							var y2 = offset + algorithm.map[y][x].lasty*LEN;
							draw_line_on_map(mapid, [x1,y1], [x2,y2], [0.5,1,0.5], 0.8);
						}
					}
				}
				// draw path from dst to src
				if (algorithm.state == DONE) {
					var x = dst[0], y = dst[1];
					if (algorithm.map[y][x].lastx != -1 && algorithm.map[y][x].lasty != -1) {
						while (x != src[0] || y != src[1]) {
							var tx = algorithm.map[y][x].lastx;
							var ty = algorithm.map[y][x].lasty;
							var offset = LEN / 2;
							var x1 = offset + x*LEN;
							var y1 = offset + y*LEN;
							var x2 = offset + algorithm.map[y][x].lastx*LEN;
							var y2 = offset + algorithm.map[y][x].lasty*LEN;
							// draw line multiple times to make line width larger
							draw_line_on_map(mapid, [x1,y1], [x2,y2], [0,1,0], 0.7);
							draw_line_on_map(mapid, [x1-1,y1], [x2-1,y2], [0,1,0], 0.7);
							draw_line_on_map(mapid, [x1+1,y1], [x2+1,y2], [0,1,0], 0.7);
							draw_line_on_map(mapid, [x1,y1-1], [x2,y2-1], [0,1,0], 0.7);
							draw_line_on_map(mapid, [x1,y1+1], [x2,y2+1], [0,1,0], 0.7);
							// tx,ty are cache for reuse x,y above
							x = tx, y = ty;
						}
					}
				}
			}
			function render() {
				step_update(BFS);
				step_update(GOAL);
				step_update(ASTAR);
				
				g2d.begin();
				
				draw_algorithm(BFS, 0);
				draw_algorithm(GOAL, 1);
				draw_algorithm(ASTAR, 2);

				// draw text
				var w = NUM*LEN+20;
				g2d.font_draw('breadth first search', map_offset[0][0], map_offset[0][1]+w);
				g2d.font_draw('target first search', map_offset[1][0], map_offset[1][1]+w);
				g2d.font_draw('A star search', map_offset[2][0], map_offset[2][1]+w);
				g2d.font_draw('press S can change start point', map_offset[0][0], map_offset[0][1]-30);
				g2d.font_draw('press D can change target point', map_offset[0][0], map_offset[0][1]-50);
				g2d.font_draw('press B can put barrier on map', map_offset[0][0], map_offset[0][1]-70);
				g2d.font_draw('press Enter will start path search', map_offset[0][0], map_offset[0][1]-90);
				g2d.font_draw(mpos, 5, 5);
				
				g2d.end();
				setTimeout(render, 30);
			}
			function to_my_coord(e) {
				return [e.clientX-8, H-e.clientY+8];
			}
			function to_grid(x, y) {
				var r = [-1, -1, -1];   // [x, y, mapid]
				var w = NUM * LEN;
				for (var i=0; i<3; i++) {
					if (x <= map_offset[i][0] || x >= map_offset[i][0] + w)   continue;
					if (y <= map_offset[i][1] || y >= map_offset[i][1] + w)   continue;
					r[0] = Math.floor((x - map_offset[i][0]) / LEN);
					r[1] = Math.floor((y - map_offset[i][1]) / LEN);
					r[2] = i;
				}
				return r;
			}
			function on_mouse_move(e) {
				var c = to_my_coord(e);
				mpos = '(' + c[0] + ',' + c[1] + ')';
			}
			function on_mouse_down(e) {
				if (e.button != 0)   return;
				var c = to_my_coord(e);
				var p = to_grid(c[0], c[1]);
				if (p[0] === -1 || p[1] === -1)   return;
				
				if (put === PUT_OBJ) {
					var x = p[0], y = p[1];
					BFS.map[y][x].passable = !BFS.map[y][x].passable;
					GOAL.map[y][x].passable = !GOAL.map[y][x].passable;
					ASTAR.map[y][x].passable = !ASTAR.map[y][x].passable;
					reset_steps();
					reset_map_state();
				} else if (put === PUT_SRC) {
					src = p;
					reset_steps();
					reset_map_state();
				} else if (put === PUT_DST) {
					dst = p;
					reset_steps();
					reset_map_state();
				}
			}
			document.onkeydown = function(e) {
				k = String.fromCharCode(e.which);
				if (k == 'S') {
					put = PUT_SRC;
					document.getElementById('put').value = 'start';
				} else if (k == 'D') {
					put = PUT_DST;
					document.getElementById('put').value = 'target';
				} else if (k == 'B') {
					put = PUT_OBJ;
					document.getElementById('put').value = 'barrier';
				} else if (e.which == 13) {   // Enter
					reset_steps();
					search_BFS(src[0], src[1], dst[0], dst[1]);
					search_GOAL(src[0], src[1], dst[0], dst[1]);
					search_ASTAR(src[0], src[1], dst[0], dst[1]);
					reset_map_state();
					BFS.state = RUN, GOAL.state = RUN, ASTAR.state = RUN;
				}
			}
		</script>
	</head>
	<body onload='init()'>
		<canvas id="canvas" style="border:none;" width='1024' height='480'></canvas>
		<br><br/>
		<tr>
			<td>click left mouse button to put <input type='text' id='put' value='barrier' readonly/>
		</tr>
	</body>
</html>